The present invention relates to the field of data acquisition, and more particularly to scanning a region.
Many scientific and engineering tasks involve scanning a region, such as an image or object, to acquire data characterizing the region. Examples of such tasks include parts inspection for automated manufacturing systems, alignment tasks for automated assembly systems, and recognition and location tasks in machine vision and motion control systems, among others.
In a typical scanning system a computer system is coupled to a camera which is operable to acquire optical or image information from a target object. The computer system may take any of various forms. The system may also include hardware and corresponding software which is operable to move one or both of the camera and the target object to perform the scan.
In robotics and motion planning an understanding of the underlying geometry of space is important. Various techniques have been developed to scan regions under various constraints or toward specific goals. In many cases the geometry is known in advance and a specific goal is desired. Examples of such goals include:
(a) Travel in the shortest time from a given point A of a space to another point B of the space.
(b) Travel the shortest path from a given point A of a space to another point B of the space.
(c) Travel a path through a space such that any point in the space is within a specified distance of the path. In other words, the space or geometry must be scanned completely or almost completely.
(d) Same as (c) but the path or trajectory may go outside of the originally given space.
(e) All the above cases but with curvature constraints added.
A more complicated situation may occur when the underlying geometry of the space is unknown and a scanning strategy must be applied to explore the structure of the space.
The tasks (a) and (b) are well-understood and classical design tools (optimal control) are available. Tasks (c) and (d) belong to a class of coverage path planning problems where a path must be determined guaranteeing that an agent will pass over every point in a given environment. Typical applications include, but are not limited to: mine-countermeasure missions, continental shelf oceanographic mapping, contamination cleanup, floor scrubbing, crop plowing, non-destructive testing, and bridge inspections, among others. Most coverage planners are still based on heuristics and the smoothness of the developed trajectories is rarely an issue.
Choset and Pignon (See Howie Choset, Philippe Pignon, Coverage Path Planning: The Boustrophedon Cellular Decomposition) have developed a boustrophedon decomposition that generalizes the concept of exact cellular decomposition and which results in a union of non-intersecting regions composing the target geometry. The coverage path planning problem is solved in elementary cells and the derived sub-paths are concatenated appropriately. The resulting schemes are essentially based on combinations of back-and-forth motions, i.e., lines are the building blocks of these strategies.
There are many other coverage algorithms, as well. In almost all cases the goal is to guide a robot or sensor to explore or to act within an environment. See, for example, J. Colgrave, A. Branch, xe2x80x9cA Case Study of Autonomous Household Vacuum Cleanerxe2x80x9d, AIAA/NASA CIRFFSS, 1994. See also M. Ollis, A. Stentz, xe2x80x9cFirst Results in Vision-Based Crop Line Trackingxe2x80x9d, IEEE International Conference on Robotics and Automation, 1996.
One promising method in motion planning is based on Morse functions. These procedures look at the critical points of a Morse function to denote the topological changes in a given space. See, for example, Howie Choset, Ercan Acar, Alfred A. Rizzi, Jonathan Luntz, xe2x80x9cExact Cellular Decompositions in Terms of Critical Points of Morse Functionsxe2x80x9d. See also Ercan U. Acar, Howie Choset, xe2x80x9cCritical Point Sensing in Unknown Environmentsxe2x80x9d. However, Morse functions find their primary use with regard to the scanning of un-smooth surfaces, and so are not generally useful for many applications.
FIGS. 1A-Dxe2x80x94Prior Art Scanning Paths
FIGS. 1A-D illustrate various scanning paths, according to the prior art. It should be noted that the physical characteristics of a scanning apparatus may place restrictions on what scanning paths may be suitable for a given application. As described below, various prior art scanning schemes may be appropriate for particular applications, but may not be generally applicable due to high curvatures and/or severe start/stop requirements.
FIG. 1Axe2x80x94Peano Curve Space-filling Path
Scanning given geometric objects in two- or higher-dimensional spaces is a well-studied topic in the mathematical literature. Space-filling curves or umbrella surfaces have often been regarded as pathological objects. Indeed, such structures are generally inappropriate for real scanning scenarios. Although space-filling is achieved in a very mathematical sense, the curves themselves are unrealizable from a motion control standpoint as they are extremely irregular. FIG. 1A illustrates a space-filling path known as a Peano Curve. As may be seen, although the Peano Curve fills the space, the complexity and extreme curvature of the path make it a poor solution for motion control applications.
Moreover, accurate space-filling is often neither attainable nor desirable in motion planning. What is needed are trajectories that pass within a specified distance of any point of the region of interest at any given time.
FIG. 1Bxe2x80x94Boustrophedon Scanning Path
One widely used scanning strategy is referred to as the boustrophedon path or xe2x80x9cway of the oxxe2x80x9d. An example of this approach is presented in FIG. 1B. The chief advantages of the boustrophedon path are the simplicity of the definition and the possibility to fill gaps in further loops. However, there are significant drawbacks to this scheme. In particular, the scanning cannot be done continuously because of curvature problems. For example, at each end of a long scan line, two 90 degree turns must be made. Such abrupt changes in motion are problematic for most motion control systems. Theoretically, the average arrival time is much worse than the strategies of the present invention, described below. The drawbacks of the boustrophedon approach are even more dramatic when searching for small objects of unknown size.
FIG. 1Cxe2x80x94Archimedes Spiral Scanning Path
The other widely used scanning strategy in practical applications is based on an Archimedes spiral. FIG. 1C illustrates one example of an Archimedes Spiral-based scanning path. As FIG. 1C demonstrates, the curvature is unbalanced, with high curvature near the center of the spiral, and low curvature near the outer edges. Additionally, this approach clearly lends itself to scanning circular regions, and is therefore unsuitable for non-circular scan regions. Other drawbacks similar to those of boustrophedon paths also apply to the Archimedes Spiral scheme, such as fixed scanning resolution or path width, which may not be suitable when scanning for small objects. Moreover, as may be seen in FIG. 1C, much time is spent scanning regions away from the center of the region.
FIG. 1Dxe2x80x94Rectangular Spiral Scanning Path
FIG. 1D illustrates a scanning scheme which utilizes features of both the boustrophedon and the spiral path approach. As FIG. 1D shows, the path comprises concentric straight-line path segments which spiral outward from the center of the region. This scheme, however, suffers from some of the shortcomings of its predecessors. For example, similar to the boustrophedon approach, there are discontinuities in the path at each corner, leading to sudden accelerations of the scanning apparatus. Furthermore, the path resolution is fixed, as with the Archimedes Spiral, and may therefore be unsuitable for objects of various or unknown sizes.
In almost all practically relevant cases, scanning schemes for more complicated geometries are based on boustrophedon paths or on other combinations of lines. This is particularly true when obstacles are part of the environment. Such obstacles may be described as holes in given regions. Topologically complex geometries, such as open sets (as opposed to simply connected objects) may also be scanned. The standard procedure is to go back-and-forth between boundaries of the resulting regions. As FIG. 1B demonstrates, such an approach is neither optimal nor acceptable from a motion control standpoint, for at least the reasons given above.
Therefore, improved systems and methods for scanning a region are desired. More specifically, scanning methods are needed which efficiently and thoroughly scan a region, possibly subject to specific curvature constraints.
The present invention comprises various embodiments of a system, method, and memory medium for scanning for an object within a region, or for locating a point within a region. Embodiments of the invention include a method for scanning for an object within a region using a conformal scanning scheme, a method for scanning for an object within a region using a Low Discrepancy Sequence scanning scheme, a method for scanning for an object within a region using a Low Discrepancy Curve scanning scheme, and a method for locating a point of interest in a region.
Conformal Mapping Embodiment
One embodiment of the invention comprises a method for scanning for an object within a region using a conformal scanning scheme. The region may have a dimensionality of one of one, two, or three, or may have a dimensionality greater than three. This method may first involve determining the characteristic geometry of the region. The method may then generate a conformal scanning curve based on the characteristic geometry of the region. Generation of the conformal scanning curve may comprise performing a conformal mapping between the characteristic geometry and a first scanning curve to generate the conformal scanning curve. The first scanning curve may be designed to minimize angle deviations and/or may be an optimum scanning curve for a first geometry, e.g., different from the characteristic geometry. The resulting conformal scanning curve may have a maximum curvature below a specified curvature value.
The method may then scan the region using a conformal scanning scheme based on the conformal scanning curve, i.e., may measure the region at a plurality of points along the conformal scanning curve. These measurements of the region produce data indicative of one or more characteristics of the object. The method may then examine the resulting data generated from the scan to determine one or more characteristics of the object and generate output indicating the one or more characteristics of the object.
Low Discrepancy Sequence Scanning
One embodiment of the invention comprises a method for scanning for an object within a region using a Low Discrepancy Sequence scanning scheme.
The method may first involve calculating a Low Discrepancy Sequence of points in the region. The region may have a dimensionality of one or two, or the region may have a dimensionality greater than two. Calculation of the Low Discrepancy Sequence of points in the region may comprise determining a plurality of points, wherein any location in the region is within a specified distance of at least one of the Low Discrepancy Sequence of points. The method may then generate a motion control trajectory from the Low Discrepancy Sequence of points.
Generation of the motion control trajectory may comprise generating a Traveling Salesman Path (TSP) from the Low Discrepancy Sequence of points, wherein the TSP includes each point of the Low Discrepancy Sequence of points, and then re-sampling the TSP to produce a sequence of motion control points comprising the motion control trajectory. Generation of the Traveling Salesman Path may comprise applying Lin""s Nearest Neighbor algorithm to the Low Discrepancy Sequence of points to generate the Traveling Salesman Path. The TSP may comprise a first sequence of points, wherein the first sequence of points defines a first trajectory having a first maximum curvature. Re-sampling the TSP may comprise manipulating the first sequence of points, which may involve adjusting point locations, discarding points, and/or generating new points, to produce the sequence of motion control points. The sequence of motion control points may define a second trajectory having a second maximum curvature which is less than the first maximum curvature. In one embodiment, the sequence of motion control points is a superset of the first sequence of points. Alternatively, the sequence of motion control points may comprise a subset of the first sequence of points and one or more additional points.
The method may then scan the region along the motion control trajectory, e.g., may measure the region at a plurality of points along the motion control trajectory. The method may then determine one or more characteristics of the object in response to the scan, and the method may generate output indicating the one or more characteristics of the object.
Low Discrepancy Curve Scanning
One embodiment of the invention comprises a method for scanning for an object within a region using a Low Discrepancy Curve scanning scheme.
The method may first involve generating a Low Discrepancy Sequence of points in the region. Generation of the Low Discrepancy Sequence of points in the region may comprise generating a plurality of points, wherein any location in the region is within a specified distance of at least one of the Low Discrepancy Sequence of points. The method may then involve calculating a Low Discrepancy Curve in the region based on the Low Discrepancy Sequence of points. In one embodiment, generation of the Low Discrepancy Sequence of points in the region and calculation of the Low Discrepancy Curve in the region based on the Low Discrepancy Sequence of points are performed offline in a preprocessing phase of the method.
After the Low Discrepancy Curve has been generated, the method may scan the region using the Low Discrepancy Curve. The scanning may be performed after the object is present in or enters the region. The scanning may comprise measuring the region at a plurality of points along the Low Discrepancy Curve. The scanning may be performed to determine one or more characteristics of the object. The method may then generate output indicating the one or more characteristics of the object resulting from the scan. Scanning or measuring the region along the Low Discrepancy Curve, as well as determining one or more characteristics of the object and generating output, may be performed in a real time phase of the method.
Generation of the Low Discrepancy Curve may be performed in various ways. In one embodiment, for each successive pair of the Low Discrepancy Sequence of points, the method may: 1) determine one or more orthogonal line segments which connect the pair of points; and 2) re-sample the one or more orthogonal line segments to generate a Low Discrepancy Curve segment. The Low Discrepancy Curve may comprise a contiguous sequence of the Low Discrepancy Curve segments from the successive pairs of the Low Discrepancy Sequence of points. In other words, the Low Discrepancy Curve segments corresponding to the successive pairs of the Low Discrepancy Sequence of points may be sequentially connected to form the Low Discrepancy Curve.
In one embodiment, the one or more orthogonal line segments may comprise a first sequence of points, wherein the first sequence of points defines a first trajectory having a first maximum curvature. In this embodiment, re-sampling the one or more orthogonal line segments may comprise manipulating the first sequence of points, which may involve adjusting point locations, discarding points, and/or generating new points, to generate the Low Discrepancy Curve segment. The resulting Low Discrepancy Curve segment may define a second trajectory having a second maximum curvature which is less than the first maximum curvature.
The re-sampling performed on the one or more orthogonal line segments may also comprise fitting a curve to a plurality of points comprised in the plurality of orthogonal line segments subject to one or more constraints, and then generating a second plurality of points along the fit curve, wherein the second plurality of points define the Low Discrepancy Curve segment.
Calculation of the Low Discrepancy Curve in the region may be performed in various ways, depending on the dimensionality of the region. In one embodiment, the region may be defined by a coordinate space having a plurality of orthogonal axes, wherein each of the plurality of orthogonal axes corresponds respectively to a dimension of the region. Each of the pair of points may have a plurality of coordinates corresponding respectively to the plurality of orthogonal axes. Also, each of the plurality of line segments may be parallel to a respective one of the orthogonal axes. Thus, each of the plurality of line segments may have a first endpoint and a second endpoint, wherein the first endpoint has a first plurality of coordinates, the second endpoint has a second plurality of coordinates, and wherein said first plurality of coordinates and said second plurality of coordinates differ only in value of a coordinate corresponding to a respective one of the plurality of orthogonal axes.
In one implementation, the one or more orthogonal line segments which connect the pair of points may comprise a contiguous sequence of the line segments corresponding to a specified order of the plurality of orthogonal axes. In this implementation, re-sampling the one or more orthogonal line segments to generate the Low Discrepancy Curve segment may comprise re-sampling the contiguous sequence of the line segments in the specified order to generate the Low Discrepancy Curve segment.
In an embodiment wherein the region is a 2-dimensional space, the plurality of orthogonal axes comprises an x axis and a y axis, and the plurality of line segments may comprise two orthogonal line segments, e.g., a first line segment and a second line segment. For example, a first of the pair of points may have two coordinates, (x0, y0), corresponding respectively to the x and y axes, and a second of the pair of points may have two coordinates, (x1, y1), corresponding respectively to the x and y axes. Each of the line segments may have a first endpoint and a second endpoint, wherein the second endpoint of the first line segment is equal to the first endpoint of the second line segment. The two orthogonal line segments which connect the pair of points may comprise a contiguous sequence of the line segments, preferably in the specified order. Also, re-sampling the two orthogonal line segments to generate a Low Discrepancy Curve segment may comprise re-sampling the contiguous sequence of the line segments in the specified order to generate the Low Discrepancy Curve segment. Where the specified order of the plurality of orthogonal axes is (x, y), the first endpoint of a first of the two line segments has coordinates (x0, y0), the second endpoint of the first of the two line segments has coordinates (x1, y0), the first endpoint of a second of the two line segments has coordinates (x1, y0), and the second endpoint of the second of the two line segments has coordinates (x1, y1). Where the specified order of the plurality of orthogonal axes is (y, x), the first endpoint of a first of the two line segments has coordinates (x0, y0), the second endpoint of the first of the two line segments has coordinates (x0, y1), the first endpoint of a second of the two line segments has coordinates (x0, y1), and the second endpoint of the second of the two line segments has coordinates (x1, y1);
In an embodiment wherein the region is a 3-dimensional space, the plurality of orthogonal axes comprises an x axis, a y axis, and a z axis, and the plurality of line segments may comprise three orthogonal line segments, e.g., a first line segment, a second line segment, and a third line segment. For example, a first of the pair of points may have three coordinates, (x0, y0, z0), corresponding respectively to the x, y, and z axes, and a second of the pair of points may have three coordinates, (x1, y1, z1), corresponding respectively to the x, y, and z axes. Each of the line segments may have a first endpoint and a second endpoint, wherein the second endpoint of the first line segment is equal to the first endpoint of the second line segment, and wherein the second endpoint of the second line segment is equal to the first endpoint of the third line segment. The three orthogonal line segments which connect the pair of points may comprise a contiguous sequence of the line segments, preferably in the specified order. Also, re-sampling the three orthogonal line segments to generate a Low Discrepancy Curve segment may comprise re-sampling the contiguous sequence of said line segments in the specified order to generate the Low Discrepancy Curve segment.
In one embodiment, the method is operable to dynamically generate new Low Discrepancy Curve segments during the scan and scan the region along these new Low Discrepancy Curve segments until desired characteristics of the object are identified. In this embodiment, the method may be operable to first generate an initial Low Discrepancy Sequence of points in the region and calculate an initial Low Discrepancy Curve segment in the region based on the first Low Discrepancy Sequence of points. These steps may be performed in a pre-processing phase. The method may then scan a portion of the region along the first Low Discrepancy Curve segment to attempt to identify a desired characteristic of the object. If the characteristic of the object is not identified, then the method may dynamically generate and add one or more new Low Discrepancy Sequence points in the region based on previous Low Discrepancy Sequence points, calculate one or more new Low Discrepancy Curve segments in the region based on the one or more new Low Discrepancy Sequence of points, and scan a portion of the region along the one or more new Low Discrepancy Curve segments to attempt to identify the characteristic of the object. The method may be operable to dynamically generate new Low Discrepancy Sequence points, calculate a new Low Discrepancy Curve segment, and scan the region along this new Low Discrepancy Curve segment one or more times in an iterative fashion until the desired characteristics in the region are identified, or until an iteration threshold has been reached.
Generating a Low Discrepancy Curve
One embodiment of the invention comprises a method for generating a Low Discrepancy Sequence curve in a region, such as a 2D rectangle, or the unit square. The method may be performed by a computer comprising a CPU and a memory medium. The memory medium may be operable to store one or more computer programs which are executable by the CPU to perform various embodiments of the method.
In one embodiment, the method may include generating an unbounded Low Discrepancy Point. As used herein, the term unbounded Low Discrepancy Point refers to a generated Low Discrepancy Point which may or may not fall within the bounds of the region. One or more boundary conditions may then be applied to the unbounded Low Discrepancy Point to generate a bounded Low Discrepancy Point, wherein the bounded Low Discrepancy Point is located within the region. In one embodiment, the generating an unbounded Low Discrepancy Point and the applying one or more boundary conditions may be repeated one or more times to generate a Low Discrepancy Sequence in the region. The generated Low Discrepancy Sequence may then be stored, and output generated, comprising the Low Discrepancy Sequence, wherein the Low Discrepancy Sequence defines the curve in the region. In one embodiment, each bounded Low Discrepancy Point of the Low Discrepancy Sequence may be store as it is generated. In one embodiment, the curve is a Low Discrepancy Curve. The method may further include scanning the region according to the curve defined by the Low Discrepancy Sequence.
In one embodiment, generating the unbounded Low Discrepancy Point may include selecting two or more irrational numbers, a step size epsilon (xcex5), and a starting position, initializing a current position to the starting position, and incrementing one or more terms of the current position based on a factor of xcex5 and one of the irrational numbers, where the incremented position is the unbounded Low Discrepancy Point. In one embodiment, the starting position may be a randomly selected point in the region. As described above, because the unbounded Low Discrepancy Point may fall outside the region, the one or more boundary conditions may be applied, generating the bounded Low Discrepancy Point, and the current position may be set to the bounded Low Discrepancy Point. It should be noted that in the iteration described above, the initializations or selections are only performed once at the beginning, i.e., the repeating said generating and said applying boundary conditions one or more times preferably comprises repeating said incrementing, said applying one or more boundary conditions, and said setting the current position, one or more times.
In one embodiment, the method may also include selecting a maximum length L of the curve in the region and initializing a current length to zero prior to said repeating. At each iteration, the current length may be updated to include a distance from the current position to the generated bounded Low Discrepancy Point. In the preferred embodiment, said repeating one or more times comprises repeating until the current length meets or exceeds the maximum length L.
In one embodiment, applying one or more boundary conditions may comprise checking if the unbounded Low Discrepancy Point is outside of the region, and if so, applying one of a reflecting boundary condition or a toroidal boundary condition at each border of the region.
Note that although the above describes an embodiment wherein the region comprises a 2-dimensional rectangular region, the two or more irrational numbers comprise two irrational numbers, and the curve in the region comprises one or more line segments, it is also contemplated that more complex curves may be generated, and that higher dimensional regions, such as unit hyper-cubes, may be used by various embodiments of the method.
Generating a Curve on a Surface
One embodiment of the comprises a method for generating a curve, such as a Low Discrepancy Curve, on a surface. In the preferred embodiment, the surface may be an abstract surface with a Riemannian metric. In one embodiment, the curve may be generated in a simple space, then mapped to the surface.
A parameterization of the surface may be selected. In the preferred embodiment, the parameter space for the parameterization is the unit square or a rectangle. Other suitable geometries for the parameter space are also contemplated, including higher dimensional unit cubes and rectangles, among others. A first curve in the parameter space may be selected, e.g., a Low Discrepancy Curve. Then, a re-parameterization of the surface may be determined or generated. For example in a preferred embodiment, a re-parameterization of the surface may be determined such that a ratio of line and area elements of the surface based on a Riemannian metric is constant.
The generated curve may be mapped onto the surface using the re-parameterization. For example, in one embodiment, the generated Low Discrepancy Curve in the unit square may be mapped onto the surface.
Finally, output may be generated comprising the mapped curve, e.g., the mapped Low Discrepancy Curve. In one embodiment, generating the output may comprise storing the curve for later use. In another embodiment, generating the output may comprise displaying the curve on a display device.
Thus, by using the above-described method, a curve, such as a Low Discrepancy Curve, generated on a unit square (or other suitable geometry) may be mapped to an abstract surface. It should be noted that any sequence, e.g., LDS, or curve, e.g., LDC generated on the unit square (or other suitable geometry) may be mapped in this way. In other words, it is not required that the sequence or curve be generated in any particular manner.
Precise Location of a Point of Interest
One embodiment of the invention comprises a method for determining a precise location of a point of interest in a region. In one embodiment, an approximate model of the region is known, and the method utilizes knowledge of this model. The region of interest may comprise a data distribution, and the point of interest may comprise an extremum of the data distribution. For example, the data distribution may comprise a Gaussian distribution, and the point of interest may comprise a Gaussian peak of the Gaussian distribution.
In one embodiment, the method may first determine or locate a region of interest in the region. Location of the region of interest may be performed in various ways, and one method is described below. The method may then determine one or more characteristics of the region of interest within the region, wherein the region of interest includes the point of interest. The one or more characteristics of the region of interest may comprise a radius of the region of interest. The one or more characteristics of the region of interest may also or instead comprise an approximate location of the point of interest, e.g., a center of the region of interest.
The method may then determine a continuous trajectory based on the one or more characteristics of the region of interest, wherein the continuous trajectory allows measurement of the region of interest. The method may then measure the region of interest at a plurality of points along the continuous trajectory to generate a sample data set. The method may then perform a surface fit of the sample data set using the approximate model to generate a parameterized surface. The method may then calculate a location of the point of interest based on the parameterized surface. The method may optionally measure the region of interest at the point of interest to confirm correctness of the calculated location. Finally, the method may generate output indicating the calculated location of the point of interest, or the calculated location of the point of interest may be provided to another program for use.
Locating the region of interest in the region may be performed in various ways. For example, the method may scan the region to locate two or more points of the region of interest, wherein each of the two or more points has associated measured data. The method may then determine a local point of interest in the region of interest proximate to the two or more points of the region of interest.
The two or more points of the region of interest may comprise an entry point and an exit point of the region of interest. In this case, the method may scan along a first scan line between the entry point and the exit point to determine the local point of interest, calculate a second scan line, wherein the second scan line passes through the local point of interest and is orthogonal to the first scan line, and measure the region along the second scan line to generate second scan line associated measured data. The method may then determine a second local point of interest along the second scan line based upon the second scan line associated measured data, determine a center of the region of interest based upon one or more of the second local point of interest and the first local point of interest, and provide a radius, wherein the region of interest comprises an area of the region within the radius of the determined center.
A system may implement any of the above methods for scanning for an object within a region, for locating a point of interest in a region, or for generating curves in a region. The system may comprise a computer system coupled to a sensor. The computer system may comprise a CPU and a memory medium, or programmable logic, which is operable to store a scanning program that implements one of the above methods. An embodiment of each of the above invention(s) may also be a software program or programs stored on a memory medium.